java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 13:33:22,896 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 13:33:22,898 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 13:33:22,910 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 13:33:22,910 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 13:33:22,911 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 13:33:22,912 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 13:33:22,913 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 13:33:22,915 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 13:33:22,916 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 13:33:22,917 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 13:33:22,917 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 13:33:22,918 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 13:33:22,919 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 13:33:22,920 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 13:33:22,921 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 13:33:22,922 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 13:33:22,924 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 13:33:22,935 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 13:33:22,936 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 13:33:22,937 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 13:33:22,940 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 13:33:22,940 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 13:33:22,940 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 13:33:22,941 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 13:33:22,942 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 13:33:22,949 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 13:33:22,950 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 13:33:22,951 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 13:33:22,951 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 13:33:22,952 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 13:33:22,952 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 13:33:22,953 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 13:33:22,953 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 13:33:22,959 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 13:33:22,959 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 13:33:22,979 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 13:33:22,980 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 13:33:22,980 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 13:33:22,980 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 13:33:22,983 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 13:33:22,984 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 13:33:22,984 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 13:33:22,984 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 13:33:22,984 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 13:33:22,985 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 13:33:22,985 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 13:33:22,985 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 13:33:22,985 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:33:22,985 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 13:33:22,986 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 13:33:22,986 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 13:33:22,986 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 13:33:22,986 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 13:33:22,986 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 13:33:22,987 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 13:33:22,988 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 13:33:22,989 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 13:33:22,990 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 13:33:23,044 INFO ]: Repository-Root is: /tmp [2018-06-25 13:33:23,062 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 13:33:23,068 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 13:33:23,070 INFO ]: Initializing SmtParser... [2018-06-25 13:33:23,070 INFO ]: SmtParser initialized [2018-06-25 13:33:23,071 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple.c.smt2 [2018-06-25 13:33:23,072 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-25 13:33:23,169 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple.c.smt2 unknown [2018-06-25 13:33:23,370 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/simple.c.smt2 [2018-06-25 13:33:23,375 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 13:33:23,382 INFO ]: Walking toolchain with 4 elements. [2018-06-25 13:33:23,382 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 13:33:23,382 INFO ]: Initializing ChcToBoogie... [2018-06-25 13:33:23,382 INFO ]: ChcToBoogie initialized [2018-06-25 13:33:23,386 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,440 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23 Unit [2018-06-25 13:33:23,440 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 13:33:23,440 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 13:33:23,441 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 13:33:23,441 INFO ]: Boogie Preprocessor initialized [2018-06-25 13:33:23,461 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,461 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,467 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,467 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,470 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,471 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,472 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... [2018-06-25 13:33:23,485 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 13:33:23,486 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 13:33:23,486 INFO ]: Initializing RCFGBuilder... [2018-06-25 13:33:23,486 INFO ]: RCFGBuilder initialized [2018-06-25 13:33:23,487 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-25 13:33:23,510 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 13:33:23,510 INFO ]: Found specification of procedure gotoProc [2018-06-25 13:33:23,510 INFO ]: Found implementation of procedure gotoProc [2018-06-25 13:33:23,511 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 13:33:23,511 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 13:33:23,511 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 13:33:23,643 INFO ]: Using library mode [2018-06-25 13:33:23,643 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:33:23 BoogieIcfgContainer [2018-06-25 13:33:23,643 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 13:33:23,654 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 13:33:23,654 INFO ]: Initializing TraceAbstraction... [2018-06-25 13:33:23,660 INFO ]: TraceAbstraction initialized [2018-06-25 13:33:23,660 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 01:33:23" (1/3) ... [2018-06-25 13:33:23,662 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1a8634ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 01:33:23, skipping insertion in model container [2018-06-25 13:33:23,662 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 01:33:23" (2/3) ... [2018-06-25 13:33:23,662 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1a8634ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 01:33:23, skipping insertion in model container [2018-06-25 13:33:23,662 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 01:33:23" (3/3) ... [2018-06-25 13:33:23,664 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 13:33:23,674 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 13:33:23,683 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 13:33:23,734 INFO ]: Using default assertion order modulation [2018-06-25 13:33:23,735 INFO ]: Interprodecural is true [2018-06-25 13:33:23,735 INFO ]: Hoare is false [2018-06-25 13:33:23,735 INFO ]: Compute interpolants for FPandBP [2018-06-25 13:33:23,735 INFO ]: Backedges is TWOTRACK [2018-06-25 13:33:23,735 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 13:33:23,735 INFO ]: Difference is false [2018-06-25 13:33:23,735 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 13:33:23,735 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 13:33:23,749 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 13:33:23,757 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 13:33:23,757 INFO ]: Found error trace [2018-06-25 13:33:23,758 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:23,758 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:23,763 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 13:33:23,766 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:23,767 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:23,798 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:23,798 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:33:23,798 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:23,841 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:23,915 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:23,917 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 13:33:23,917 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 13:33:23,919 INFO ]: Interpolant automaton has 3 states [2018-06-25 13:33:23,935 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 13:33:23,935 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:33:23,947 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 13:33:24,023 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:24,023 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 13:33:24,023 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 13:33:24,025 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 13:33:24,025 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:24,033 INFO ]: With dead ends: 9 [2018-06-25 13:33:24,033 INFO ]: Without dead ends: 9 [2018-06-25 13:33:24,035 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 13:33:24,051 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 13:33:24,064 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 13:33:24,065 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 13:33:24,066 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 13:33:24,069 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 13:33:24,069 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:24,069 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 13:33:24,069 INFO ]: Interpolant automaton has 3 states. [2018-06-25 13:33:24,069 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 13:33:24,070 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 13:33:24,070 INFO ]: Found error trace [2018-06-25 13:33:24,070 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:24,070 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:24,070 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 13:33:24,070 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:24,070 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:24,071 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:24,071 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:33:24,071 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:24,093 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:24,203 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:24,204 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:24,204 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:24,213 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:33:24,263 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:24,270 INFO ]: Computing forward predicates... [2018-06-25 13:33:24,566 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:24,598 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:33:24,598 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-25 13:33:24,598 INFO ]: Interpolant automaton has 4 states [2018-06-25 13:33:24,598 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-25 13:33:24,598 INFO ]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-06-25 13:33:24,599 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 4 states. [2018-06-25 13:33:24,617 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:24,617 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 13:33:24,617 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 13:33:24,617 INFO ]: Start accepts. Automaton has 4 states. Word has length 8 [2018-06-25 13:33:24,617 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:24,617 INFO ]: With dead ends: 10 [2018-06-25 13:33:24,617 INFO ]: Without dead ends: 10 [2018-06-25 13:33:24,618 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-06-25 13:33:24,618 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 13:33:24,619 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 13:33:24,619 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 13:33:24,620 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 13:33:24,620 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 13:33:24,621 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:24,621 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 13:33:24,621 INFO ]: Interpolant automaton has 4 states. [2018-06-25 13:33:24,621 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 13:33:24,621 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 13:33:24,621 INFO ]: Found error trace [2018-06-25 13:33:24,621 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:24,621 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:24,621 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 13:33:24,621 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:24,621 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:24,622 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:24,622 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:33:24,622 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:24,647 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:24,849 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:24,849 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:24,849 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:24,857 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:33:24,897 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:33:24,897 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:24,900 INFO ]: Computing forward predicates... [2018-06-25 13:33:25,373 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:25,392 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:33:25,393 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-25 13:33:25,393 INFO ]: Interpolant automaton has 6 states [2018-06-25 13:33:25,393 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-25 13:33:25,393 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-25 13:33:25,393 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 6 states. [2018-06-25 13:33:25,578 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:25,579 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-25 13:33:25,580 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 13:33:25,580 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-25 13:33:25,580 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:25,580 INFO ]: With dead ends: 11 [2018-06-25 13:33:25,580 INFO ]: Without dead ends: 11 [2018-06-25 13:33:25,580 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-25 13:33:25,581 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-25 13:33:25,582 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-25 13:33:25,582 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-25 13:33:25,582 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-25 13:33:25,582 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 9 [2018-06-25 13:33:25,582 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:25,582 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-25 13:33:25,582 INFO ]: Interpolant automaton has 6 states. [2018-06-25 13:33:25,582 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-25 13:33:25,582 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-25 13:33:25,582 INFO ]: Found error trace [2018-06-25 13:33:25,582 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:25,583 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:25,583 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 3 times [2018-06-25 13:33:25,583 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:25,583 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:25,585 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:25,585 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:33:25,585 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:25,629 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:25,767 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:25,767 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:25,767 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:25,773 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 13:33:25,833 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 13:33:25,833 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:25,836 INFO ]: Computing forward predicates... [2018-06-25 13:33:27,844 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:27,879 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:33:27,879 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-25 13:33:27,880 INFO ]: Interpolant automaton has 8 states [2018-06-25 13:33:27,880 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-25 13:33:27,880 INFO ]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-06-25 13:33:27,880 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 8 states. [2018-06-25 13:33:28,003 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:28,003 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 13:33:28,003 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-25 13:33:28,003 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-25 13:33:28,003 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:28,003 INFO ]: With dead ends: 12 [2018-06-25 13:33:28,003 INFO ]: Without dead ends: 12 [2018-06-25 13:33:28,004 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2018-06-25 13:33:28,004 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 13:33:28,005 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 13:33:28,005 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 13:33:28,005 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 13:33:28,005 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-25 13:33:28,006 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:28,006 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 13:33:28,006 INFO ]: Interpolant automaton has 8 states. [2018-06-25 13:33:28,006 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 13:33:28,006 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 13:33:28,006 INFO ]: Found error trace [2018-06-25 13:33:28,006 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:28,006 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:28,006 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 4 times [2018-06-25 13:33:28,006 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:28,006 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:28,007 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:28,007 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:33:28,007 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:28,038 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:28,191 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:28,191 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:28,191 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:28,196 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 13:33:28,230 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 13:33:28,230 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:28,233 INFO ]: Computing forward predicates... [2018-06-25 13:33:32,989 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:33,019 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:33:33,020 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2018-06-25 13:33:33,020 INFO ]: Interpolant automaton has 10 states [2018-06-25 13:33:33,020 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-25 13:33:33,020 INFO ]: CoverageRelationStatistics Valid=32, Invalid=58, Unknown=0, NotChecked=0, Total=90 [2018-06-25 13:33:33,020 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 10 states. [2018-06-25 13:33:33,200 WARN ]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 5 [2018-06-25 13:33:34,075 WARN ]: Spent 767.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 12 [2018-06-25 13:33:35,006 WARN ]: Spent 809.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 16 [2018-06-25 13:33:35,167 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:35,167 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-25 13:33:35,167 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-25 13:33:35,167 INFO ]: Start accepts. Automaton has 10 states. Word has length 11 [2018-06-25 13:33:35,168 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:35,168 INFO ]: With dead ends: 13 [2018-06-25 13:33:35,168 INFO ]: Without dead ends: 13 [2018-06-25 13:33:35,168 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 34 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=83, Invalid=127, Unknown=0, NotChecked=0, Total=210 [2018-06-25 13:33:35,168 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-25 13:33:35,170 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-25 13:33:35,170 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-25 13:33:35,170 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-25 13:33:35,170 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-25 13:33:35,170 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:35,170 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-25 13:33:35,170 INFO ]: Interpolant automaton has 10 states. [2018-06-25 13:33:35,171 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-25 13:33:35,171 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-25 13:33:35,171 INFO ]: Found error trace [2018-06-25 13:33:35,171 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:35,171 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:35,171 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 5 times [2018-06-25 13:33:35,171 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:35,171 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:35,172 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:35,172 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:33:35,172 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:35,210 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:35,424 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:35,424 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:35,424 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:35,432 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 13:33:35,512 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-25 13:33:35,512 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:35,515 INFO ]: Computing forward predicates... [2018-06-25 13:33:38,105 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:38,124 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:33:38,149 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-25 13:33:38,149 INFO ]: Interpolant automaton has 11 states [2018-06-25 13:33:38,149 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-25 13:33:38,149 INFO ]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-06-25 13:33:38,150 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 11 states. [2018-06-25 13:33:38,402 WARN ]: Spent 136.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 19 [2018-06-25 13:33:38,629 WARN ]: Spent 219.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 16 [2018-06-25 13:33:38,792 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:38,792 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-25 13:33:38,792 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-25 13:33:38,792 INFO ]: Start accepts. Automaton has 11 states. Word has length 12 [2018-06-25 13:33:38,792 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:38,793 INFO ]: With dead ends: 15 [2018-06-25 13:33:38,793 INFO ]: Without dead ends: 15 [2018-06-25 13:33:38,793 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=107, Invalid=199, Unknown=0, NotChecked=0, Total=306 [2018-06-25 13:33:38,793 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-25 13:33:38,794 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-25 13:33:38,794 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-25 13:33:38,799 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-25 13:33:38,799 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 12 [2018-06-25 13:33:38,799 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:38,799 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-25 13:33:38,799 INFO ]: Interpolant automaton has 11 states. [2018-06-25 13:33:38,799 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-25 13:33:38,799 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-25 13:33:38,799 INFO ]: Found error trace [2018-06-25 13:33:38,799 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:38,799 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:38,799 INFO ]: Analyzing trace with hash 726730004, now seen corresponding path program 6 times [2018-06-25 13:33:38,800 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:38,800 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:38,800 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:38,800 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:33:38,800 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:38,869 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:39,703 WARN ]: Spent 597.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 12 [2018-06-25 13:33:39,882 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:39,882 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:39,882 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:39,905 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 13:33:39,940 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-25 13:33:39,940 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:39,943 INFO ]: Computing forward predicates... [2018-06-25 13:33:40,444 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 59 DAG size of output: 16 [2018-06-25 13:33:44,372 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:44,396 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:33:44,396 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2018-06-25 13:33:44,396 INFO ]: Interpolant automaton has 13 states [2018-06-25 13:33:44,396 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-25 13:33:44,397 INFO ]: CoverageRelationStatistics Valid=48, Invalid=108, Unknown=0, NotChecked=0, Total=156 [2018-06-25 13:33:44,397 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 13 states. [2018-06-25 13:33:44,778 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:44,778 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-25 13:33:44,778 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 13:33:44,778 INFO ]: Start accepts. Automaton has 13 states. Word has length 14 [2018-06-25 13:33:44,779 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:44,779 INFO ]: With dead ends: 16 [2018-06-25 13:33:44,779 INFO ]: Without dead ends: 16 [2018-06-25 13:33:44,779 INFO ]: 0 DeclaredPredicates, 30 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=133, Invalid=247, Unknown=0, NotChecked=0, Total=380 [2018-06-25 13:33:44,779 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-25 13:33:44,781 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-25 13:33:44,781 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-25 13:33:44,781 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-25 13:33:44,781 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-06-25 13:33:44,781 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:44,781 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-25 13:33:44,781 INFO ]: Interpolant automaton has 13 states. [2018-06-25 13:33:44,781 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-25 13:33:44,782 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-25 13:33:44,782 INFO ]: Found error trace [2018-06-25 13:33:44,782 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:44,782 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:44,782 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 7 times [2018-06-25 13:33:44,782 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:44,782 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:44,783 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:44,783 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 13:33:44,783 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:44,837 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:45,380 WARN ]: Spent 146.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 14 [2018-06-25 13:33:45,463 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:45,463 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:45,463 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:45,472 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:33:45,503 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:45,506 INFO ]: Computing forward predicates... [2018-06-25 13:33:46,646 WARN ]: Spent 218.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 11 [2018-06-25 13:33:46,767 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:33:53,680 WARN ]: expecting exponential blowup for input size 6 [2018-06-25 13:33:53,972 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:53,993 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 13:33:53,993 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 15 [2018-06-25 13:33:53,993 INFO ]: Interpolant automaton has 15 states [2018-06-25 13:33:53,993 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-25 13:33:53,993 INFO ]: CoverageRelationStatistics Valid=49, Invalid=161, Unknown=0, NotChecked=0, Total=210 [2018-06-25 13:33:53,994 INFO ]: Start difference. First operand 16 states and 16 transitions. Second operand 15 states. [2018-06-25 13:33:54,980 WARN ]: Spent 308.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 27 [2018-06-25 13:33:54,981 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 13:33:54,981 INFO ]: Finished difference Result 18 states and 18 transitions. [2018-06-25 13:33:54,981 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-25 13:33:54,981 INFO ]: Start accepts. Automaton has 15 states. Word has length 15 [2018-06-25 13:33:54,983 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 13:33:54,983 INFO ]: With dead ends: 18 [2018-06-25 13:33:54,983 INFO ]: Without dead ends: 18 [2018-06-25 13:33:54,984 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 8 SyntacticMatches, 4 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=192, Invalid=408, Unknown=0, NotChecked=0, Total=600 [2018-06-25 13:33:54,984 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-25 13:33:54,985 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-25 13:33:54,985 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-25 13:33:54,986 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 18 transitions. [2018-06-25 13:33:54,986 INFO ]: Start accepts. Automaton has 18 states and 18 transitions. Word has length 15 [2018-06-25 13:33:54,986 INFO ]: Finished accepts. word is rejected. [2018-06-25 13:33:54,986 INFO ]: Abstraction has 18 states and 18 transitions. [2018-06-25 13:33:54,986 INFO ]: Interpolant automaton has 15 states. [2018-06-25 13:33:54,986 INFO ]: Start isEmpty. Operand 18 states and 18 transitions. [2018-06-25 13:33:54,986 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-25 13:33:54,986 INFO ]: Found error trace [2018-06-25 13:33:54,986 INFO ]: trace histogram [10, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 13:33:54,986 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 13:33:54,986 INFO ]: Analyzing trace with hash 1509090572, now seen corresponding path program 8 times [2018-06-25 13:33:54,986 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 13:33:54,986 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 13:33:54,987 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:54,987 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 13:33:54,987 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 13:33:55,067 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:55,846 WARN ]: Spent 496.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 14 [2018-06-25 13:33:56,131 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 15 [2018-06-25 13:33:56,537 INFO ]: Checked inductivity of 55 backedges. 1 proven. 54 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 13:33:56,537 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 13:33:56,537 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:33:56,558 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 13:33:56,605 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 13:33:56,605 INFO ]: Conjunction of SSA is unsat [2018-06-25 13:33:56,609 INFO ]: Computing forward predicates... [2018-06-25 13:34:07,326 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-25 13:34:28,353 INFO ]: Timeout while computing interpolants [2018-06-25 13:34:28,554 WARN ]: Destroyed unattended storables created during the last iteration: 10 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 13:34:28,554 WARN ]: Verification canceled [2018-06-25 13:34:28,558 WARN ]: Timeout [2018-06-25 13:34:28,558 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 01:34:28 BoogieIcfgContainer [2018-06-25 13:34:28,558 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 13:34:28,559 INFO ]: Toolchain (without parser) took 65184.02 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 264.2 MB in the beginning and 543.0 MB in the end (delta: -278.8 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:34:28,560 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 13:34:28,560 INFO ]: ChcToBoogie took 57.97 ms. Allocated memory is still 308.8 MB. Free memory was 264.2 MB in the beginning and 262.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:34:28,561 INFO ]: Boogie Preprocessor took 44.66 ms. Allocated memory is still 308.8 MB. Free memory was 262.2 MB in the beginning and 260.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:34:28,561 INFO ]: RCFGBuilder took 157.70 ms. Allocated memory is still 308.8 MB. Free memory was 260.2 MB in the beginning and 252.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-25 13:34:28,562 INFO ]: TraceAbstraction took 64904.37 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 252.2 MB in the beginning and 543.0 MB in the end (delta: -290.8 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 13:34:28,563 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 308.8 MB. Free memory is still 274.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 57.97 ms. Allocated memory is still 308.8 MB. Free memory was 264.2 MB in the beginning and 262.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 44.66 ms. Allocated memory is still 308.8 MB. Free memory was 262.2 MB in the beginning and 260.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 157.70 ms. Allocated memory is still 308.8 MB. Free memory was 260.2 MB in the beginning and 252.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 64904.37 ms. Allocated memory was 308.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 252.2 MB in the beginning and 543.0 MB in the end (delta: -290.8 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 18 with TraceHistMax 10, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was transforming 0 conjuction. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 64.8s OverallTime, 9 OverallIterations, 10 TraceHistogramMax, 4.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 56 SDtfs, 24 SDslu, 192 SDs, 0 SdLazy, 79 SolverSat, 54 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 161 GetRequests, 53 SyntacticMatches, 19 SemanticMatches, 89 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 286 ImplicationChecksByTransitivity, 8.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=18occurred in iteration=8, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 8 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 25.5s InterpolantComputationTime, 165 NumberOfCodeBlocks, 165 NumberOfCodeBlocksAsserted, 25 NumberOfCheckSat, 150 ConstructedInterpolants, 0 QuantifiedInterpolants, 9970 SizeOfPredicates, 28 NumberOfNonLiveVariables, 905 ConjunctsInSsa, 265 ConjunctsInUnsatCore, 15 InterpolantComputations, 1 PerfectInterpolantSequences, 0/198 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/simple.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_13-34-28-575.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/simple.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_13-34-28-575.csv Completed graceful shutdown